Weighted fair queuing, (also known as packetized general processor sharing (PGPS), may be come important in the next generation of ATM switching system and routers in order to fairly share bandwidth while allowing for a guaranteed minimum delay to individual connections sharing a particular transmission facility. However, to date, the implementation of weighted fair queuing algorithms have been problematic and difficult to scale to a large number of connections. For example, in conventional weighted fair queuing, the complexity of an ideal implementation is 0(N)+0(logN) where N is the number of circuits, 0(N) represents the recalculation for all head-of-line packets for all circuits, and 0(logN) is the amount of calculations involved in resorting all of the reference finishing times. The next generation of ATM switches is expected to include tens of thousands of connections and operate at multi-gigabit rates. Accordingly, a scalable, highly efficient implementation of a weighted fair queuing algorithm is necessary.